package java学习.代码随想录.动态规划;

import java.util.Arrays;
import java.util.concurrent.locks.ReentrantLock;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/8/29 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 打家劫舍 {

    public static  int rob(int[] nums) {
        int bagsize = nums.length%2 ==0?nums.length/2:nums.length/2 +1;

        int []dp = new int[bagsize+1];

        for (int i = 2; i < nums.length;i++ ) {
            for (int j = bagsize; j >=nums[i] ; j--) {
//              偷：第 i 件物品：  dp[j] = dp[i-2]+nums[i]
//              不偷第 i 件物品：  dp[j] = dp[i-1];
                dp[j] = Math.max(dp[i-2]+nums[i],dp[i-1]);
            }

        }
        System.out.println(Arrays.toString(dp));

        return  dp[bagsize] ;
    }
    /**
     * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
     *      如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
     *              0 1  2 3
     * 示例 1： 输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。   偷窃到的最高金额 = 1 + 3 = 4 。
                    0 1 2 3 4
     * 示例 2： 输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。   偷窃到的最高金额 = 2 + 9 + 1 = 12 。
        0 不偷 1 偷
     dp[0] = dp[i-1],dp[i-2]+p[i]
     */

    /**
     *  因为取得数字不能相邻，故 bagsize = n % 2==0? n/2:n/2 +1 ;
     *  在背包为 bagsize 上 物品最大价值。取得物品不能相邻
     *
     * 打家劫舍不是背包问题。
     */
    /**
     * 1. dp[i] i个之前房间偷的最大值
     * 2. 偷、不偷。
     *  ·   偷：第 i 件物品：  dp[j] = dp[i-2]+nums[i]
     *       不偷第 i 件物品：  dp[j] = dp[i-1];
     * 3. dp[0] = nums[0] 偷第0家
     *    dp[1] = max(nums[0],nums[1]) 偷第1家
     * 4. 由于 dp[j] 源于 dp[i-2] and dp[i-1];故 从前到后
     *
     */
    public static  int rob1(int[] nums){
        if (nums.length==1){
            return nums[0];
        }
        int []dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1] );
        }
        System.out.println(Arrays.toString(dp));
        return dp[nums.length-1];
    }
    public static  int rob2(int[] nums){
        if (nums.length==1){
            return nums[0];
        }
        return  dfs(nums,0);
    }

//    递归
    public static int dfs(int[] nums, int index) {
        if(index>=nums.length){
            return 0;
        }
        int result= 0;
        // 不偷
        result=   dfs(nums,index+1);
//        偷，然后去下下家
        result = Math.max(result,dfs(nums,index+2 )+nums[index]);
        return result;
    }
    public static int MaxSumSubArray(int[] nums) {
        // 我是Java选手
        int size = nums.length;
        int [] dp = new int[size];
        dp[0] = nums[0];
        dp[1] = Math.max(dp[0], nums[1]);
        for (int i = 2; i < size; i++) {
            dp[i] = Math.max(dp[i-1], nums[i]+dp[i-2]);
        }
        System.out.println(Arrays.toString(dp));
        return dp[size-1];
    }

    public static void main(String[] args) {
        int[] n = {1,2,3,1};
        int[] n1 = {2,7,9,3,1};
        System.out.println(rob2(n1));
        System.out.println("---------");
        System.out.println(rob1(n1));
        System.out.println("---------");
        System.out.println(MaxSumSubArray(n1));
        int a = 2,b=5,c=10;
        System.out.println(a+b+""+(a+b)+c);
    }
}
